1. Field of Invention
This invention relates generally to content addressable memories.
2. Description of Related Art
Content addressable memories (CAMs) are frequently used for address look-up functions in Internet data routing. For example, routers used by local Internet Service Providers (ISPs) typically include one or more CAMs for storing a plurality of Internet addresses and associated data such as, for instance, corresponding address routing information. When data is routed to a destination address, the destination address is compared with all CAM words, e.g., Internet addresses, stored in the CAM array. If there is a match, routing information corresponding to the matching CAM word is output and thereafter used to route the data.
A CAM includes an array of memory cells arranged in a matrix of rows and columns. Each memory cell stores a single bit of digital information, where the bits stored in a row of memory cells constitute a CAM word. During compare operations, a comparand word is received at appropriate input terminals of the CAM and then compared with all the CAM words. For each CAM word that matches the comparand word, a corresponding match line signal is asserted to indicate a match condition. If any of the match line signals are asserted, a match flag is asserted, and the index or address of the matching CAM word is read from the CAM. If there are multiple matches, a multiple match flag is asserted.
Each row of the CAM array includes an additional memory cell for storing a valid bit indicative of whether a valid word is stored in that row. The valid bits are used to control which words stored in the CAM array "participate" in the compare operation with the comparand word. When a valid bit is asserted, the result of a compare operation between the comparand word and data stored in the corresponding row affects assertion of the match flag for the array. That is, when the valid bit is asserted, a match condition between the comparand word and the corresponding data results in assertion of the match flag. Conversely, when the valid bit is de-asserted, the match line is de-asserted and the result of the compare operation does not affect assertion of the match flag. Thus, data is invalidated by de-asserting the corresponding valid bit.
The valid bits are also used to generate a full flag indicative of whether the CAM array is full. A de-asserted full flag indicates that at least one of the rows in the CAM array is available and, conversely, an asserted full flag indicates that there are no available rows in the array (i.e., the array is full).
FIG. 1 shows a typical CAM row 1 as having n CAM cells 10(1)-10(n) to store an n-bit CAM word, and also includes a valid bit cell 15 for storing the valid bit for the row 1. The CAM cells 10(1)-10(n) and valid bit cell 15 are each coupled to an associated match line ML. A weak pull-up transistor 16 is coupled between a supply voltage V.sub.DD and the match line ML. The transistor 16 has a gate tied to ground potential, and therefore remains in a conductive state.
During compare operations between an n-bit comparand word and an n-bit CAM word stored in the CAM cells 10(1)-10(n) of the row 1, the match line ML corresponding to the CAM row 1 is pre-charged to the supply voltage V.sub.DD via the weak pull-up transistor 16. The n-bits of the comparand word are compared with corresponding bits of the CAM word in respective CAM cells 10(1)-10(n). If all bits of the comparand word match corresponding bits of the CAM word stored in the row 1, the match line ML remains charged at approximately V.sub.DD, thereby indicating a match condition for the row 1. If, however, any of the comparand bits does not match its corresponding CAM bit, the associated CAM cell 10 pulls the match line ML toward ground potential, thereby indicating a mismatch condition for the row 1.
During the compare operation between the comparand word and data stored in the row 1, the valid bit stored in the valid cell 15 is compared to a reference bit in a manner similar to that described above with respect to the CAM cells 10(1)-10(n). Typically, the reference bit is set to an asserted state. Thus, when the valid bit stored in the valid bit cell 15 is asserted and therefore matches the reference bit, the valid bit cell 15 does not discharge the match line ML, thereby allowing the match line ML to indicate the result of the compare operation between the comparand word and CAM word. Conversely, when the valid bit is de-asserted and therefore does not match the reference bit, the valid bit cell 15 pulls the match line ML toward ground potential, thereby forcing a mismatch condition between the comparand word and the CAM word. In this manner, the de-asserted valid bit precludes a match condition between the comparand word and the CAM word from affecting assertion of the match flag, thereby invalidating the CAM word.
As described above, the match lines ML of a typical CAM array are automatically pre-charged to the supply voltage V.sub.DD for each compare operation, irrespective of whether each row contains valid data. Thus, when the row 1 contains invalid data, as indicated by the valid bit stored in the valid bit cell 15, the corresponding match line ML is unnecessarily charged and then discharged during every compare operation. Current flow associated with this unnecessary charging and discharging of such match lines results in undesirable power consumption. When CAM arrays are only partially full at any given time, this undesirable power consumption may become significant.